#include <vector>
#include <iostream>

using namespace std;

class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        if (nums.size() == 0) {
            return {};
        }
        int element[4] = {nums[0], 0, nums[0], 0};
        for (int num : nums) {
            if (num == element[0]) {
                element[1]++;
            } else if (num == element[2]) {
                element[3]++;
            } else {
                if (element[1] == 0) {
                    element[0] = num;
                    element[1] = 1;
                } else if (element[3] == 0) {
                    element[2] = num;
                    element[3] = 1;
                } else {
                    element[1]--;
                    element[3]--;
                }
            }
        }
        int count[2] = {0};
        for (int num : nums) {
            if (num == element[0]) {
                count[0]++;
            } else if (num == element[2]) {
                count[1]++;
            }
        }
        vector<int> ans;
        if (count[0] > nums.size() / 3) {
            ans.push_back(element[0]);
        }
        if (count[1] > nums.size() / 3) {
            ans.push_back(element[2]);
        }
        return ans;
    }
};

int main() {
    vector<int> input = {2,2,9,3,9,3,9,3,9,3,9,3,9,3,9,3,9};
    Solution solution;
    vector<int> output = solution.majorityElement(input);
    for (int val : output) {
        cout << val << endl;
    }
    return 0;
}